import java.util.ArrayList;

/**
 * This class represents a Radix Sorter
 * @author Matthew Dye
 *
 * @param <K>
 */
public class MSDRadixSorter<V> {
	
	/**
	 * This will call the helper function to recursively sort the arr passed in
	 * @param arr to be sorted
	 * @return The sorted array
	 */
	@SuppressWarnings("unchecked")
	public HashNode<String,V>[] sort(HashNode<String,V>[] arr)
	{
		ArrayList <HashNode<String,V>> list = new ArrayList<HashNode<String,V>>();
		for(int i = 0; i<arr.length; i++)
		{
			list.add(arr[i]);
		}
		list = MSDHelper(list,0);
		arr = list.toArray((HashNode<String,V>[]) new HashNode[list.size()]);
		return arr;
	}
	/**
	 * Recursively sorts the array passed in based on the key using the Radix Sorted Methodology
	 * @param arr To be sorted
	 * @param curPlace Current index of character to be sorted
	 * @return Sorted array
	 */
	public ArrayList<HashNode<String,V>> MSDHelper(ArrayList<HashNode<String,V>> arr, int curPlace)
	{
		@SuppressWarnings("unchecked")
		ArrayList<HashNode<String,V>> out = new ArrayList<HashNode<String,V>>();
		ArrayList<HashNode<String,V>>[] buckets = (ArrayList<HashNode<String,V>>[]) new ArrayList[129];
		HashNode<String,V>[] nodes = arr.toArray((HashNode<String,V>[]) new HashNode[arr.size()]);
		HashNode<String,V>[] tempNodes;
		
		for(HashNode<String,V> node : nodes)
		{
			if(node.getKey().length() <= curPlace)
			{
				if(buckets[0] == null)
					buckets[0] = new ArrayList<HashNode<String,V>>();
				buckets[0].add(node);
			}
			else
			{
				if(buckets[(int) node.getKey().charAt(curPlace)] == null)
					buckets[(int) node.getKey().charAt(curPlace)] = new ArrayList<HashNode<String,V>>();
				buckets[(int) node.getKey().charAt(curPlace)].add(node);
			}
		}
		int count = 0;
		for(ArrayList<HashNode<String,V>> list : buckets)
		{
			if(list!=null)
			{
				if(list.size()>1)
				{
					list = MSDHelper(list,curPlace +1);
				}
				count++;
			}
		}
		
		for(ArrayList<HashNode<String,V>> list : buckets)
		{
			if(list!=null)
			{
				tempNodes = list.toArray((HashNode<String,V>[]) new HashNode[list.size()]);
				for(HashNode<String,V> node : tempNodes)
				{
					out.add(node);
				}
			}
		}
		arr = out;
		return arr;
		
	}
	/**
	 * Removes the duplicate values in the array
	 * @param arr Array to be checked
	 * @return Array without duplicates
	 */
	public HashNode<String,V>[] removeDuplicates(HashNode<String,V>[] arr)
	{
		int removed = arr.length;
		for(int i = 1; i <arr.length; i++)
		{
			if(arr[i-1].getKey().equals(arr[i].getKey()))
			{
				 arr[i-1] = null;
				 removed--;
			}
		}
		HashNode<String,V>[] newArr = (HashNode<String,V>[]) new HashNode[removed];
		int index = 0;
		int indexOld = 0;
		while(indexOld < arr.length)
		{
			if(arr[indexOld] != null)
			{
				newArr[index] = arr[indexOld];
				index++;	
			}
			indexOld++;
			
		}
		return newArr;
	}
	/**
	 * Returns the value where the key equals the passed in key
	 * @param key Target
	 * @param arr Array to be checked
	 * @return Value where the key equals the one passed in
	 */
	public V get(String key, HashNode<String,V>[] arr)
	{
		V outValue = null;
		boolean found = false;
		int index = 0;
		while(index < arr.length && !found)
		{
			if(arr[index].getKey().equals(key))
			{
				outValue = arr[index].getValue();
				found = true;
			}
			index++;
		}
		return outValue;	
	}
	/**
	 * Searches for the passes in key to see if it exists in the passed in array
	 * @param key Target
	 * @param arr Array to be checked
	 * @return True if the key exists, false if not
	 */
	public boolean contains(String key, HashNode<String,V>[] arr)
	{

		
		boolean found = false;
		int index = 0;
		while(index < arr.length && !found)
		{
			if(arr[index].getKey().equals(key))
			{
				found = true;
			}
			index++;
		}
		return found;	
	}
	/**
	 * This will add a new node in sorted ordered to the passed in array
	 * @param key New Key
	 * @param val New value
	 * @param arr Array to be manipulated
	 * @return Array with the new node inserted
	 */
	public HashNode<String,V>[] add(String key, V val, HashNode<String,V>[] arr)
	{
		@SuppressWarnings("unchecked")
		HashNode<String,V>[] newArray = java.util.Arrays.copyOf(arr,arr.length+1);
		//HashNode<String,V>[] newArray = (HashNode<String,V>[])new HashNode[arr.length+1];;
		int index = 0;
		while(arr[index].getKey().compareTo(key) < 0)
		{
			newArray[index] = arr[index];
			index++;
		}
		newArray[index] = new HashNode<String,V>(key,val);
		index++;
		for(index = index;index<newArray.length;index++)
		{
			newArray[index] = arr[index-1];
		}
		return newArray;
	}

}
